// 核心代码模式
class Solution {
public:
    int Fibonacci(int n) {
        if (n ==0 || n==1){
            return n;
        }
           //思路1：递归
//         else{
//             return Fibonacci(n-1)+Fibonacci(n-2);
//         }

        //思路2：动态规划
        int a = 0, b = 1;
        int c;
        for (int i=2;i<=n;i++){
            c = b;
            b = a+b;
            a = c;
        }
        return b;

        //或者存在数组里
//         for (int i=2; i<=n; ++i) {
//             dp[i] = dp[i-1] + dp[i-2];//状态转移方程
//         }
//         return dp[n];
    }
};